Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS245 Programming Languages / 2016-Fall / Notebooks

1. Summary of Basic Scheme

1.1 Thinking Recursively, Summary

  1. Decide on the base cases
  2. A base case is the "smallest" or "simplest" case
  3. After that, assume that the function exists, and use it
  4. Divide the problem up into smaller pieces
In [1]:
(define snoc
  (lambda (item lst)
    (cond
     ((null? lst) (cons item '()))
     (else (cons (car lst) 
                 (snoc item (cdr lst)))))))
In [2]:
(snoc 1 '()) ;; -> (1)
Out[2]:
(1)
In [3]:
(snoc 'a '(c b)) ;; -> (c b a)
Out[3]:
(c b a)
In [4]:
(snoc '4 '(1 2 3)) ;; -> (1 2 3 4)
Out[4]:
(1 2 3 4)
In [5]:
(define rac
  (lambda (lst)
    (cond
     ((null? lst) (error 'rac "can't take the rac of an empty list"))
     ((null? (cdr lst)) (car lst))
     (else (rac (cdr lst))))))
In [6]:
(rac '(1 2 3 4)) ;; -> 4
Out[6]:
4
In [7]:
(rac '(a)) ;; -> a
Out[7]:
a
In [8]:
(rac '())


Traceback (most recent call last):
  File "In [8]", line 1, col 1, in 'rac'
  File "In [5]", line 4, col 19, in 'error'
  File "In [5]", line 4, col 19
RunTimeError: Error in 'rac': can't take the rac of an empty list

1.2 Scheme Functions

Scheme (like Python) can take functions as arguments, and return them. This is called "functions as first-class objects."

In [9]:
(define add1
  (lambda (number)
    (+ 1 number)))
In [10]:
(map add1 '(1 2 3))
Out[10]:
(2 3 4)
In [11]:
(define my-map
  (lambda (f lst)
    (cond
     ((null? lst) '())
     (else (cons (f (car lst))
                 (my-map f (cdr lst)))))))
In [12]:
(my-map add1 '(1 2 3))
Out[12]:
(2 3 4)
In [16]:
(map + '(1 2 3) '(3 4 5) '(100 100 100))
Out[16]:
(104 106 108)

1.3 Higher-Order Functions

In [20]:
(define compose
  (lambda (f g)
    (lambda (lst)
      (f (g lst)))))
In [21]:
(define my-cadr (compose car cdr)) ;; my-cadr is a <procedure>
In [22]:
(my-cadr '(1 2 3)) ;; -> 2
Out[22]:
2
In [23]:
(map my-cadr '((1 2 3) (4 5 6) (7 8 9)))
Out[23]:
(2 5 8)

1.4 What is a Programming Language?

  1. a computer program
  2. takes in source code in a language (often recursively defined)
  3. produces either a compiled program, or interpreter

Lab03 will begin the process of implementing Scheme in Python.

In [24]:
(import "math")
Out[24]:
(math)
In [25]:
(math.pow 2 3)
Out[25]:
8.0
In [26]:
(define expt math.pow)
In [27]:
(expt 3 5)
Out[27]:
243.0